class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

    def _pre_order(self, recursion=False):
        #  breakpoint()
        res = ""
        if not recursion:
            res += str(self.val)
            if self.left:
                res += self.left._pre_order()
            if self.right:
                res += self.right._pre_order()
            return res
        else:
            stack = []
            node = self
            while node or stack:
                while node:
                    # the left tree are pushed consequently
                    res += str(node.val)
                    stack.append(node)
                    node = node.left
                if stack:
                    node = stack.pop()
                    node = node.right
            return res

    def _in_order(self, recursion=False):
        res = ""
        if not recursion:
            if self.left:
                res += self.left._in_order()
            res += str(self.val)
            if self.right:
                res += self.right._in_order()
            return res
        else:
            stack = []
            node = self
            while node or stack:
                while node:
                    stack.append(node)
                    node = node.left
                if stack:
                    node = stack.pop()
                    # after popped, the node value will be added.
                    res += str(node.val)
                    node = node.right
            return res

    def _post_order(self, recursion=False):
        res = ""
        if not recursion:
            if self.left:
                res += self.left._post_order()
            if self.right:
                res += self.right._post_order()
            res += str(self.val)
            return res
        else:
            node = self
            stack = []
            while node or stack:
                while node:
                    # the left tree are pushed consequently
                    res += str(node.val)
                    stack.append(node)
                    node = node.right
                if stack:
                    node = stack.pop()
                    node = node.left
            # After the above circling, we get the order: root->right->left,
            # if we reverse it, we can get the post_order: left->right->root
            # Reverse the result
            return res[::-1]

    def order(self, mode="pre_order", recursion=False):
        """the string when call print(TreeNOde).

        Args:
            mode: must be one of those:
            ["pre_order","in_order","post_order"]
        """
        tmp_str = "#"
        if mode == "pre_order":
            tmp_str += self._pre_order(recursion)
        elif mode == "in_order":
            tmp_str += self._in_order(recursion)
        elif mode == "post_order":
            tmp_str += self._post_order(recursion)
        else:
            raise ValueError(r"mode must be in [pre_order,in_order,post_order]")
        return tmp_str


if __name__ == "__main__":
    node1 = TreeNode(1)
    node2 = TreeNode(2)
    node3 = TreeNode(3)
    node4 = TreeNode(4)
    node5 = TreeNode(5)

    """
        1
      2   3
     5 4
     pre_order  : 12543
     in_order   : 52413
     post_order : 54231
    """
    node1.left = node2
    node1.right = node3
    node2.right = node4
    node2.left = node5

    pre_order_sequence = node1.order(mode="pre_order", recursion=False)
    pre_order_sequence_recursion = node1.order(mode="pre_order", recursion=True)

    in_order_sequence = node1.order(mode="in_order", recursion=False)
    in_order_sequence_recursion = node1.order(mode="in_order", recursion=True)

    post_order_sequence = node1.order(mode="post_order", recursion=False)
    post_order_sequence_recursion = node1.order(mode="post_order", recursion=True)

    print("pre_order:", (pre_order_sequence_recursion == pre_order_sequence))
    print("in_order:", (in_order_sequence_recursion == in_order_sequence))
    print("post_order:", (post_order_sequence_recursion == post_order_sequence))
